package com.czk.search;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 二分查找法
 *
 * @Author:ChenZhangKun
 * @Date: 2020/7/1 20:38
 */
public class BinarySearch {
    public static void main(String[] args) {
        int[] array = {5, 4, 3, 3, 3, 2, 1};
        //System.out.println(binarySearch(array, 0, array.length - 1, 6));
        int i = binarySearchPra(array, 0, array.length - 1, 3);
        List<Integer> list = mulBinarySearchPra(array, 0, array.length - 1, 3);
        System.out.println(list);
        System.out.println(i);
    }

    /**
     * 只有单个的情况
     *
     * @param array
     * @param left
     * @param right
     * @param value
     * @return
     */
    public static int binarySearch(int[] array, int left, int right, int value) {
        // 找到返回索引
        // 没有找到返回-1
        if (left > right) {
            return -1;
        }
        // 拿到中间下标
        int mid = (left + right) / 2;
        int num = array[mid];
        if (num < value) {
            // 向右递归
            return binarySearch(array, mid + 1, right, value);
        } else if (value < num) {
            // 向左递归
            return binarySearch(array, left, mid - 1, value);
        } else {
            return mid;
        }

    }

    /**
     * 递归二分法的练习
     *
     * @param array
     * @param left
     * @param right
     * @param value
     * @return
     */
    public static int binarySearchPra(int[] array, int left, int right, int value) {
        // 没找到的退出条件
        if (left > right) {
            // 没找到
            return -1;
        }
        // 二分法
        int mid = (left + right) / 2;
        // 拿到值
        int temp = array[mid];
        if (temp < value) {
            // 向右
            left = mid + 1;
            return binarySearchPra(array, left, right, value);
        } else if (temp > value) {
            // 向左
            right = mid - 1;
            return binarySearchPra(array, left, right, value);
        } else {
            // 找到索引
            return mid;
        }
    }

    /**
     * 多个相同值得情况
     *
     * @param array
     * @param left
     * @param right
     * @param value
     * @return
     */
    public static List<Integer> binarySearch_2(int[] array, int left, int right, int value) {
        // 找到返回索引
        // 没有找到返回-1
        if (left > right) {
            return new ArrayList<>();
        }
        // 拿到中间下标
        int mid = (left + right) / 2;
        int num = array[mid];
        if (num < value) {
            // 向右递归
            return binarySearch_2(array, mid + 1, right, value);
        } else if (value < num) {
            // 向左递归
            return binarySearch_2(array, left, mid - 1, value);
        } else {
            // 找到该值
            List<Integer> list = new ArrayList<>(5);
            // 先加入集合
            list.add(mid);
            // 循环查找左边的值
            int temp = mid - 1;
            while (true) {
                if (temp < 0 || array[temp] != value) {
                    break;
                } else {
                    list.add(temp);
                    temp--;
                }
            }
            // 循环查找右边的值
            int temp_1 = mid + 1;
            while (true) {
                if (temp_1 > array.length - 1 || array[temp_1] != value) {
                    break;
                } else {
                    list.add(temp_1);
                    temp_1++;
                }
            }
            // 返回该集合
            return list;
        }

    }

    /**
     * 二分法查找多个值的索引
     *
     * @param array
     * @param left
     * @param right
     * @param value
     * @return
     */
    public static List<Integer> mulBinarySearchPra(int[] array, int left, int right, int value) {
        if (left > right) {
            return new ArrayList<>();
        }
        int mid = (left + right) / 2;
        // 拿到值
        int temp = array[mid];
        if (temp > value) {
            left = mid + 1;
            return mulBinarySearchPra(array, left, right, value);
        } else if (temp < value) {
            right = mid - 1;
            return mulBinarySearchPra(array, left, right, value);
        } else {
            // 找到值
            List<Integer> list = new ArrayList<>();
            // 加入集合
            list.add(mid);
            // 定义接收左边的值
            int i = mid - 1;
            while (i >= 0 && array[i] == value) {
                // 加入集合
                list.add(i);
                i--;
            }
            // 定义接收右边的值
            int j = mid + 1;
            while (j <= array.length - 1 && array[j] == value) {
                list.add(j);
                j++;
            }
            Collections.sort(list);
            return list;
        }
    }
}
